package 似包非包;

/**
 * @Date 2024/6/4 9:36
 * @description: 力扣96: 不同的二叉搜索树
 * .
 * @Author LittleNight
 */
public class likou96 {
    public int numTrees(int n) {
        // 根据分析问题的过程中, 发现重复子问题, 抽象出来一个状态表示
        // dp[i]: 节点个数为 i 的时候, 一共有多少种二叉搜索树
        int[] dp = new int[n + 1];
        dp[0] = 1; // 初始化, 根据实际情况, dp[1] = 1反推出dp[0] = 1.

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                // 左子树的节点数是 j - 1, 右子树的节点数是 i - j
                // 排列组合方式, 所以是乘法. (详解看视频)
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}
